/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/
 * 300. 最长递增子序列
 * medium, 赖德檀 2024.09.09
 * 动态规划
 */
 class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int>dp(nums.size(),1);
        for(int i=1;i<nums.size();i++)
        for(int j=0;j<=i;j++)
        {
            if(nums[j]<nums[i])
            {
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};